bipartite graph decision
OK if the DFS paints over and no discrepancies occur.
Since the "if and only if u is red, then v is blue" diff relation holds for sides u and v, UnionFind can be used to determine the sufficiency of the relation.
---
This page is auto-translated from /nishio/二部グラフ判定 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.